In a communication system, information is transmitted from a transmitter, over a channel, to a receiver. For example, in a wireless communication system, a transmitter in a mobile device may transmit information over a wireless channel to a receiver in a base station.
The channel may introduce errors into the information transmitted over the channel. Error control coding may be used to detect and/or correct the errors. For example, k bits of information to be transmitted from a transmitter to a receiver may first be encoded by an encoder in the transmitter to obtain a codeword having a length of Nb bits, where Nb>k. The codeword may then be transmitted over the channel. The received codeword is then decoded by a decoder in the receiver to obtain a decision as to which k bits were transmitted. The redundancy added by transmitting a codeword of bit length Nb>k increases the probability that the k bits are correctly decoded at the receiver, even if some errors were introduced into the codeword by the noise in the channel.
There are different types of error detecting and correcting codes. One type of error correcting code, referred to as an Arikan polar code, is disclosed in the paper “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels” by E. Arikan, IEEE Transactions on Information Theory, vol. 55, no. 7 (July 2009). The Arikan polar code is a binary polar code, which means that the Arikan polar code only performs error control coding on a binary symbol alphabet. The k bits that are encoded using the Arkian polar code represent k information symbols. Each one of the k information symbols can only take on one of two values.
Also, the bit length Nb of each codeword in the Arikan polar code must be a power of two, i.e. Nb=2n, where n is a natural number. However, due to the coding rate requirement, the codeword length that can be actually transmitted into the channel may not be exactly the bit length Nb=2n.